\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size

\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage[UTF8]{ctex}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{tikz}
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template
\usepackage{clrscode}
\usepackage{sectsty} % Allows customizing section commands
\usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usetikzlibrary{graphs}
\usetikzlibrary{shapes.arrows}
\allsectionsfont{\centering \normalfont\scshape} % Make all sections centered, the default font and small caps
%\allsectionsfont{\indent\normalfont\scshape} % Make all sections centered, the default font and small caps
\usepackage{indentfirst}
\setlength{\parindent}{2em}
\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header

\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\usepackage[linesnumbered,boxed,lined,ruled,vlined]{algorithm2e}
\usepackage{algorithmicx}
\usepackage{algpseudocode}

\usepackage{graphicx}
\usepackage{float}
%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{中国科学院大学}\ \textsc{计算机与控制学院} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge 算法设计与分析第四次作业 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}

\author{黎吉国} % Your name

\date{\normalsize\today} % Today's date or a custom date

\begin{document}

\maketitle % Print the title
\newpage

\section{Airplane Landing Problem}
\begin{enumerate}
  \item  Variables\\
  $x_i$:denote $x_i$ as the time of landing for airplane $i$.\\
  $n$:denote $n$ is the number of the total plane.
  \item Constrains\\
  $[s_i,t_i]$:$[s_i,t_i]$ is the landing time window for airplane $i$.\\
  we have
  \[
  s_i \le x_i \le t_i,\ \ i=1,2,\ldots,n
  \]
  \[ x_{i+1}-x_{i}\ge z \ \ i=1,2,\ldots,n-1 \]
  \item Objective\\
  get the landing time for every airplane, which maximize the mininum gap between successive landing
  \[maximize\ z\]
  \item Formalization
  \[
  \begin{split}
    max\ &\ z\\
    s.t.\ &\ s_i\le x_i \le t_i\quad i=1,2,3,\ldots,n-1,n\\
    & x_{i+1}-x_{i}\ge z \ \ i=1,2,\ldots,n-1
  \end{split}
  \]
  \item Instance\\
  \[
  \begin{split}
    n:\quad &3\\
    [s_i,t_i]:\quad &[8:00,9:00]\\
    &[9:20,10:00]\\
    &[10:10,10:30]
  \end{split}
  \]
  可得：\\
  \[
  \begin{split}
    x1&=8:00\\
    x2&=9:20\\
    x3&=10:30\\
    z&=70
  \end{split}
  \]
\end{enumerate}
\newpage
\section{gas station placement}
\begin{itemize}
  \item varibles\\
  $n:$the number for towns.\\
  $x_i:$the distance for $ith$ gas station.\\
  $z:$ the maximal distance for successive gas station.
  \item constrains\\
  \[ d_i-r \le x_i \le d_i+r \ \ i=1,2,\ldots,n \]
  \[ x_{i+1}-x_i\le z \]
  \item objective \\
  \[ minimize\  z \]
  \item formalization\\
  \[
  \begin{split}
    min &\quad z\\
    s.t. &\quad d_i-r \le x_i \le d_i+r \ \ i=1,2,\ldots,n\\
    &\quad x_{i+1}-x_i\le z\ \ i=1,2,\ldots,n-1\\
  \end{split}
  \]
\end{itemize}

\newpage
\section{Simplex algorithm}
implement simplex algorithm with matlab.\\
代码及测试如下：
\lstset{language=Matlab}%代码语言使用的是matlab
\lstset{breaklines}%自动将长的代码行换行排版
\lstset{extendedchars=false}%解决代码跨页时，章节标题，页眉等汉字不显示的问题
\begin{lstlisting}[frame=single]
  function [x,z]=simplex( A,b,c );
  %z=min cx
  %Ax<=b
  %x>=0

  %get the initial B, we set it as B,N
  [row,cloumn]=size(A);
  temp=1:cloumn;
  B_idx=temp>cloumn-row;
  N_idx=(1-B_idx)>0;

  x=zeros(cloumn,1);
  z=0;
  b1=b;
  c1=c;
  flag=0;
  A1=A;
  B_order=[cloumn-row+1:cloumn];

  while(1)
  idx_in_temp=find_base_in(c1(N_idx));
  if idx_in_temp<0
      flag=1;%done
      break;
  else
      if idx_in_temp==0
          flag=0;%done many solution
          break;
      end
  end
  idx_in_1=find(N_idx);
  idx_in=idx_in_1(idx_in_temp);
  idx_out_temp=find_base_out(b1,A1(:,idx_in));
  if idx_out_temp<0
      flag=-1;%infty
      break;
  end
  idx_out=B_order(idx_out_temp);
  B_order(idx_out_temp)=idx_in;

  [B_idx(idx_in) B_idx(idx_out)]=deal(B_idx(idx_out),B_idx(idx_in));
  N_idx=(1-B_idx)>0;
  B_o=A1(:,B_order);
  A1=B_o\A1;
  b1=B_o\b1;

  z=z-c1(idx_in).*b1(idx_out_temp);
  c1 = c1-c1(idx_in).*transpose(A1(idx_out_temp,:));

  end
  if flag==1
      display('get the optimal solution');
      x=zeros(cloumn,1);
      x(B_order)=b1;
  else
      if flag==-1
          display('opt is infty');
      else
          display('many solution');
      end
  end

  end

  function [idx]=find_base_in(C_N);
      if isempty(C_N)
          idx=-1;
          return;
      end
      [min_value,idx_1]=min(C_N);
      if min_value<0
          idx=idx_1(1);
      else if min_value==0
              idx=0;
          else
              idx=-1;
          end
      end
      idx=int8(idx);
  end

  function [idx]=find_base_out(b1,A_i);
      A_n=A_i<0;
      if A_n
          idx=-1;%infty
          return;
      end
      A_i(A_i==0)=A_i(A_i==0)+eps;
      [min_value,idx_1]=min(b1./A_i);
      idx=idx_1(1);
      idx=uint8(idx);
  end
\end{lstlisting}
测试如下：
\begin{enumerate}
  \item 有最优解的情况
  \[
  \begin{split}
    min &\quad -x_1-14 x_2- 6 x_3\\
    s.t.&\quad x_1+x_2+x_3\le 4\\
    &\quad x_1 \le 2\\
    &\quad x_3\le 3\\
    &\quad 3x_2_+x_3\le 6\\
    &\quad x_1,x_2,x_3 \ge 0
  \end{split}
  \]
  \begin{lstlisting}[frame=single]
    [x,z]=simplex(A,b,c)
get the optimal solution

x =

        0
   1.0000
   3.0000
        0
   2.0000
   0.0000
        0


z =

   32
  \end{lstlisting}
  \item 无最优解情况
  \[
  \begin{split}
    min &\quad -x_1-x_2\\
    s.t.&\quad x_1-x_2\le 1\\
    &\quad -x_1+x_2 \le 1\\
    &\quad x_1,x_2\ge 0
  \end{split}
  \]
  \begin{lstlisting}[frame=single]
  >> [x,z]=simplex(A1,b1,c1)
  opt is infty

  x =

       0
       0
       0
       0
  z =
     Inf
  \end{lstlisting}

  \item 无穷多最优解
  \[
  \begin{split}
    min &\quad -x_1-x_2\\
    s.t.&\quad x_1-x_2\le 1\\
    &\quad -x_1+x_2 \le 1\\
    &\quad x_1+x_2 \le 1 \\
    &\quad x_1,x_2\ge 0
  \end{split}
  \]
  \begin{lstlisting}[frame=single]
  >> [x,z]=simplex(A1,b1,c1)
  many solution

  x =

       0
       1
       0
       0


  z =

     1
  \end{lstlisting}
\end{enumerate}



\end{document}
